package syf.tree;

import java.util.Arrays;

public class HeapRank {
    public static void main(String[] args) {
        //升序，构建成大顶堆
        int[] arr={4,6,8,5,9,-1,48,-999,14};
        //降序，构建成小顶堆
        heapRank(arr);
    }
    /**
     * 堆排序
     * @param arr 待排序的数组
     *            叶子节点个数 arr.length/2-1
     */
    public static void heapRank(int[] arr){
        int tmp;
        //顶堆排好
        for (int i= arr.length/2-1;i>=0;i--) {
            adjustHeap(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));
        //进行排序
        for (int i=arr.length-1;i>0;i--){
            tmp=arr[0];
            arr[0]=arr[i];
            arr[i]=tmp;
            adjustHeap(arr, 0,i);
        }
        System.out.println(Arrays.toString(arr));
    }
    //将一个数组，调整成一个大顶堆
    /**
     * 完成将以i对应的叶子节点的树调整成大顶堆
     * 举例：int[] arr={4,6,8,5,9}; => i=1 adjustHeap => 得到 {4，9，8，5，6} => {9，6，8，5，4}
     * @param arr 待调整的数组
     * @param i 非叶子节点在数组中的索引
     * @param length 表示对多少个元素进行调整，逐渐减少
     */
    //思路：根据传进来的i从下往上开始判断，存储的临时变量只会再for结束完成后赋值，这样可以减少交换的次数，因为再他交换的下面可能有比他更大的，
    //每次以当前节点的子节点跳转，也就是 n为当前节点的下标 2*n+1
    public static void adjustHeap(int[] arr,int i,int length){
       int tmp=arr[i];
       for (int j=2*i+1;j<length;j=2*j+1){
           if (j+1<length){
               if (arr[j]<arr[j+1])
                   j++;
               if (tmp<arr[j]){
                   arr[i]=arr[j];
                   i=j;
               }
           }
       }
       arr[i]=tmp;
    }
}
/*
*  //临时变量，存放非叶子节点的值
        int tmp=arr[i];
        //开始遍历树，2*i+1为i的左子节点，这次完成后如果还有，下一次就是该子节点的子节点
        for (int j=2*i+1;j<length;j=2*j+1){
            //先判断不要越界 重要！！！！！！！！！！！！ （两个都要包上，否则不满足条件时，还是会进行交换 ）
            if (j+1<length) {
                //和该非叶子节点的子节点大小，并得到该值的下标
                //arr[j]为左子节点  arr[j+1]为右子节点
                if (arr[j]<arr[j+1]){
                    j++;
                }
                //查看非叶子节点的值是否小于子节点，小于的话用子节点覆盖，先不交换，因为还有可能下面的比该值大
                if (tmp<arr[j]){
                    arr[i]=arr[j];
                    i=j;
                }else {
                    //由于我们是由下网上，因此大小满足时可直接退出
                    break;
                }
            }
        }
        //当for循环结束后，再赋值
        arr[i]=tmp;
* */